#pragma once
#include <iostream>
#include <assert.h>

namespace ys
{
	template<class Iterator, class Ref, class Ptr>
	class ReverseIterator
	{
	public:
		typedef ReverseIterator<Iterator, Ref, Ptr> self;
		ReverseIterator(Iterator it) :_it(it) {}

		self& operator++() { --_it; return *this; }
		self operator++(int) { self temp = *this; --_it; return temp; }
		Ref operator*() { Iterator cur = _it; return *(--cur); }
		bool operator!=(const self& s) { return _it != s._it; }
	public:
		Iterator _it;
	};
	template<class T>
	class vector
	{
	public:
		typedef T value_type;
		typedef T* iterator;
		typedef const T* const_iterator;

		typedef ReverseIterator<iterator, value_type&, value_type*> reverse_iterator;
		typedef ReverseIterator<const_iterator, const value_type&, const value_type*> const_reverse_iterator;
	public:
		//-----------------------------------------------------//
		iterator begin() { return _start; }
		iterator end() { return _finish; }
		const iterator begin() const { return _start; }
		const iterator end() const { return _finish; }

		reverse_iterator rbegin() { return reverse_iterator(end()); }
		reverse_iterator rend() { return reverse_iterator(begin()); }
		const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
		const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
		//-----------------------------------------------------//
		vector() {}
		vector(size_t n, const value_type& val = value_type())
		{
			reserve(n);
			while (n--)
			{
				push_back(val);
			}
		}
		vector(const ys::vector<T>& v)
		{
			int n = v.size();
			reserve(v.capacity());
			for (int i = 0; i < n; i++)
			{
				push_back(v[i]);
			}
		}
		vector(iterator begin, iterator end)
		{
			int n = end - begin;
			reserve(n);
			while(start != end)
			{
				push_back(*start);
				start++;
			}
		}
		~vector()
		{
			delete[] _start;
			_start = nullptr;
			_finish = nullptr;
			_end_of_storage = nullptr;
		}
		//-----------------------------------------------------//
		inline size_t size() { return _finish - _start; }
		inline size_t capacity() { return _end_of_storage - _start; }
		inline bool empty() { return _finish == _start; }

		inline const size_t size() const { return _finish - _start; }
		inline const size_t capacity() const { return _end_of_storage - _start; }
		inline const bool empty() const { return _finish == _start; }

		void reserve(size_t num)
		{
			if (num < size()) return;
			if (num < capacity()) { _end_of_storage = _start + num; return; }

			size_t offset = size();
			value_type* tmp = new value_type[num];
			for (size_t i = 0; i < offset; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;

			_start = tmp;
			_finish = _start + offset;
			_end_of_storage = _start + num;
		}

		void resize(size_t n, const value_type& val = value_type())
		{
			if (n <= size()) { _end_of_storage = _finish = _start + n; }
			else if (n <= capacity())
			{
				n -= size();
				for (size_t i = 0; i < n; i++)
				{
					_start[size() + i] = val;
					_finish++;
				}
				_end_of_storage = _start + n;
				return;
			}
			else
			{
				value_type* tmp = new T[n];
				int i = 0;
				for (; i < size(); i++)
				{
					tmp[i] = _start[i];
				}
				for (; i < n; i++)
				{
					tmp[i] = val;
				}
				delete[] _start;

				_start = tmp;
				_end_of_storage = _finish = _start + n;
			}
		}
		//-----------------------------------------------------//
		iterator insert(iterator pos, const value_type& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			size_t offset = pos - _start;
			if (_finish == _end_of_storage)
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			pos = _start + offset;

			iterator tail = end();
			while (tail != pos)
			{
				*tail = *(tail - 1);
				tail--;
			}
			*pos = val;
			_finish++;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos);
			assert(!empty());
			assert(pos >= _start);
			assert(pos <= _finish);

			iterator tail = pos + 1;
			while (tail != end())
			{
				*(tail - 1) = *tail;
				tail++;
			}
			_finish--;
		}

		void push_back(const value_type& val)
		{
			insert(end(), val);
		}
		void pop_back()
		{
			assert(!empty());
			_finish--;
		}
		//-----------------------------------------------------//
		inline T& operator[](size_t i) { assert(i < size()); return _start[i]; }
		inline const T& operator[](size_t i) const { assert(i < size()); return _start[i]; }

		void swap(vector<value_type>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
};